package Sort;

/**
 * @author chetaifu
 */
public class OptimizeQuickSort {
    private OptimizeQuickSort(){}

    public static void sort(Comparable[] arr){
        sort(arr, 0, arr.length -1);
    }

    private static void sort(Comparable[] arr, int low, int high){
        if(low >= high){
            return;
        }

        // 插入排序优化
        if(high - low <= 15){
            insertSort(arr, low, high);
            return;
        }

        int p = partition(arr, low, high);
        sort(arr, low, p - 1);
        sort(arr, p + 1, high);
    }

    /** 对arr[l...r]部分进行partition操作
     * 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p] */
    private static int partition(Comparable[] arr, int low, int high){
        // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
        swap(arr, low, (int) (Math.random() * (high - low + 1)) + low);

        Comparable v = arr[low];
        int j = low;
        for (int i = low + 1; i <= high; i++) {
            if (arr[i].compareTo(v) < 0) {
                j ++;
                swap(arr, i, j);
            }
        }
        swap(arr, low, j);
        return j;
    }

    private static void swap(Object[] arr, int i, int j){
        Object tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    private static void insertSort(Comparable[] array, int low, int high){
        Comparable tmp;
        int j;
        for (int i = low + 1; i <= high ; i++) {
            tmp = array[i];
            for (j = i - 1; j >= low && array[j].compareTo(tmp) > 0; j--) {
                array[j + 1] = array[j];
            }
            array[j + 1] = tmp;
        }
    }
}
